#include <iostream>
#include <string.h>
#include <time.h>
int fibo(int n);

//本算法是对带dp 数组的动态规划数组的优化
//因为每次fibo计算只涉及到俩个数字，没有必要建立一个完整的数组。
int fibo(int n)
{
    //dp数组的动态规划从f(1), f(2)自底向上往上推
    //dp[1], dp[2], dp[3], ... dp[n]
    int prev = 1;
    int curr = 1;
    for(int i = 3; i <= n; i++)
    {
        int temp = curr + prev;
        prev = curr;
        curr = temp;
    }
    return curr;
}
int main()
{
    using namespace std;
    int begin = clock();
    cout << fibo(45) << endl;
    int end = clock();
    cout << "using " << end - begin << endl;
    return 0;
}
// 1 1 2 3 5 8 13 21 